package com.linearList;

/**
 * @Author: linKe
 * @Date: 2021/12/30 9:41
 * @FileName: SinglyList
 * @version: 1.0
 * @Description: 循环单链表类定义
 * 将最后一个结点的next域指向head，形成环形结构，就是循环单链表
 */
public class SinglyListCycle<T> {

    /**
     * 头指针，表示单链表的开始
     */
    public Node<T> head;

    /**
     * 构造空单链表
     */
    public SinglyListCycle() {
        //创建头结点，data和next值均为null
        this.head = new Node<T>();
        //初始空循环单链表
        this.head.next = this.head;
    }

    /**
     * 构造单链表 有values数组提供元素，忽略其中空对象
     *
     * @param values 对象数组
     */
    public SinglyListCycle(T[] values) {
        //创建空单链表
        this();
        //rear 指向单链表最后一个结点
        Node<T> rear = this.head;
        //若values.length==0,构造空链表
        for (int i = 0; i < values.length; i++) {
            //但values数组的值 不会null是   增加单链表的结点
            if (values[i] != null) {
                //尾插入，创建结点链入rear结点之后   更改插入结点的指向
                rear.next = new Node<T>(values[i], null);
                //rear指向新的链尾结点
                rear = rear.next;
                //增加一个循环指向 最终rear指向为head    尾指向
                rear.next = this.head;
            }
        }
    }

    /**
     * 判断单链表是否为空，O（1）
     *
     * @return 结果
     */
    boolean isEmpty() {
        //判断头结点的后继指向是否为空 为空时返回true
        //return this.head.next == null;
        //更改为判断头结点的指向是否为自身，空循环则返回true
        return this.head.next == this.head;
    }

    /**
     * 返回第i个元素，0≤i<表长度。若i越界返回null。O（n）
     *
     * @param i 结点的顺序索引
     * @return 结果
     */
    T get(int i) {
        //初始结点赋值 头结点的后继节点赋值为p   this.head.next;变更为循环单链后 等效为this.head了
        //Node<T> p = this.head.next;
        //
        Node<T> p = this.head;
        //遍历单链表，寻找第i个节点（p的指向    对应的后继结点值） 之前输成1了
        //p.next != this.head 判断条件修改为 指向不为头结点
        for (int j = 0; p.next != this.head && j < i; j++) {
            //p的后继结点赋值
            p = p.next;
        }
        //若i指向第i个节点，返回其元素值  否则返回null
        //return (i >= 0 && p != null) ? p.data : null;
        //  同上  遍历最后一个值不能正常返回
        //return (i >= 0 && p.next != this.head) ? p.data : null;
        //  修改判断条件结点数据值 为空
        return (i >= 0 && p.data != null) ? p.data : null;

    }

    /**
     * 设置第i个元素为x，0≤i<n。若i越界，抛出符号越界异常：若x==null，抛出空对象异常
     *
     * @param i 结点的顺序索引
     * @param x 结点的元素值
     */
    void set(int i, T x) {
        if (x == null) {
            //抛出空对象异常
            throw new NullPointerException("x==null");
        }
        //初始结点赋值
        //Node<T> p = this.head.next;
        //
        Node<T> p = this.head;
        //遍历寻找第i个结点 增加p的非空判断 进行前后结点的后继指向更改
        // p.next != this.head 同上
        for (int j = 0; p.next != this.head && j < i; j++) {
            //逐个结点值替换   顺次后移
            p = p.next;
        }
        //if (i >= 0 && p != null) {
        if (i >= 0 && p.next != this.head ) {
            //p指向第i个结点 赋值为x
            p.data = x;
        } else {
            //抛出下标序号越界异常
            throw new IndexOutOfBoundsException(i + "");
        }

    }

    /**
     * 返回结点的元素长度
     *
     * @return 结果
     */
    int size() {
        //初始计量变量i
        int i = 0;
        /*
        遍历链表所有元素  p的后继结点不为null作为循环条件
        p.next !=null 实际判断的是结点p
        * */
        //for (Node<T> p = this.head.next; p != null; p = p.next) {
        //
        for (Node<T> p = this.head; p.next != this.head; p = p.next) {
            //计量结果增加
            i++;
        }
        //返回结点计量结果
        return i;
    }


    /**
     * 插入结点对象
     * 前一个结点front的后继指向新插入的结点p
     * 插入结点p的后继指向原front的后继结点
     * 对序号i采取容错措施，若i<0,插入x在最前;若i>n，插入x在最后。
     *
     * @param x 结点元素索引
     * @return 结果
     */
    Node<T> insert(int i, T x) {
        if (x == null) {
            //返回空对象异常
            throw new NullPointerException("x==null");
        }
        //初始化前结点对象  front
        //Node<T> front = this.head.next;
        //
        Node<T> front = this.head;
        //遍历链表元素 寻找第i个元素
        //for (int j = 0;front!=null && j < i; j++) {
        //实际寻找的第i-1个元素或者尾结点（front指向）
        //for (int j = 0; front.next != null && j < i; j++) {
        //
        for (int j = 0; front.next != this.head && j < i; j++) {
            //结点赋值  后继指向赋给前结点
            front = front.next;
        }
        //当前结点不为null时
        //if (front != null){
        //新插入的结点而不是当前结点
        //if (front.next != null){  不需要非空判断，上边遍历的时候已经判断过
        //新插入的结点赋值 修改结点的前后指向
        //front.next = new Node<>(front.data, front.next);
        //将插入的元素值赋给新结点
        //front.next = new Node<>(x, front.next);
        //
        front.next = new Node<>(x, front.next);
        //}
        //返回新插入的结点对象
        //return front;
        return front.next;
    }

    /**
     * 删除第i个结点对象
     * pre 的后继指向 为 pre.next.next
     * 移除pre.next结点
     *
     * @param i 链表顺序索引
     * @return 结点
     */
    T remove(int i) {
        //初始结点赋值
        //Node<T> front = this.head.next;
        //
        Node<T> front = this.head;
        //遍历寻找第i个结点对象
        //if (front.next!=null){
        //增加i序号的值判断
        //for (int j = 0;front!=null&& j < i; j++) {
        //寻找的是i-1的结点（front指向）
        //for (int j = 0; front.next != null && j < i; j++) {
        //
        for (int j = 0; front.next != this.head && j < i; j++) {
            front = front.next;
        }
        // front.next != this.head  这个会出现最后一个指向 的值判断结果为false
        //
        if (i >= 0 && front.data != null) {
            //获取旧的后继指向元素值
            T old = front.next.data;
            //顺延结点后继指向
            front.next = front.next.next;
            //返回删除的结点元素值
            return old;
        }
        //删除结点不存在返回null
        return null;
    }

    /**
     * 元素结点搜索，根据元素值进行结点值匹配，返回最先匹配的结点对象
     *
     * @param key 元素值
     * @return 结果
     */
    Node<T> search(T key) {
        //初始化结点p 并遍历已存在的结点
        //for (Node<T> p = this.head.next; p != null; p = p.next) {
        //
        for (Node<T> p = this.head.next; p != this.head; p = p.next) {
            //p.data.equals(key); 增加if判断 返回
            if (key.equals(p.data)) {
                return p;
            }
        }
        return null;
    }

    /**
     * 重写equals比较方法
     *
     * @param obj 比较对象
     * @return 结果
     */
    @Override
    public boolean equals(Object obj) {
        //对象地址值指向比较 相等返回true
        if (obj == this) {
            return true;

        }
        //比较对象类型是否一致，不一致则返回false
        if (!(obj instanceof SinglyListCycle<?>)) {
            return false;
        }
        //获取进行对象比较的结点   p
        Node<T> p = this.head.next;
        //传入对象进行比较的结点   q
        Node<?> q = ((SinglyListCycle<?>) obj).head.next;
        //遍历循环比较
        //while (p != null && q != null && q.data.equals(p.data)) {
        while (p.next != this.head && q.next != this.head && q.data.equals(p.data)) {
            p = p.next;
            q = q.next;
        }
        //返回pq都为空对象的结果（表明两个链表相等），及最终都遍历完毕
        //return p != null && q != null;
        // 比较两个结点是否 都是尾端的结点
        //  p.next == this.head && q.next == this.head 因为头结点为空 这里直接判断为false
        //  更改为 同时空值的结点（不对，循环链表没有null出现）
        //  比较两者的头结点的数据值
        return p.next.data == null && q.next.data == null;
    }
}
